In modern electronic distribution networks, message authentication is an important objective of information security. This objective is met by providing the receiver of a message an assurance of the sender's identity. As physical protection such as sealed envelopes is not possible for messages expressed as binary sequences, digital tools have been developed using cryptography. A major weakness of all cryptographic methods for message authentication lies in their use of algorithms with fixed symmetric or public keys. We describe a new key transport scheme, based on secret sharing, which allows each new message to be authenticated with a new key, strengthening the system's resistance to attacks on the key or messages.
Authentication is one of the four most important objectives of information security. The others are confidentiality, data integrity and non-repudiation. In communication networks, some or all of these objectives may need to be met.
With respect to confidentiality, it will be noted that there are applications where information should be kept secret. Encryption techniques provide confidentiality by transforming data into unintelligible format. This is a reversible process, and the entity in possession of the right key can recover the data.
With respect to data integrity, users need to have assurance that information has not been altered in an unauthorized way. Hashing functions, which produce compact representations of data, are commonly used for checking data integrity.
Finally, with respect to non-repudiation, when a dispute arises a result of a party in denial of an action, e.g., involvement an electronic transaction, it can be resolved with the participation of a trusted third party acting as a judge.
There are two basic types of authentication: ‘entity’ authentication and ‘message’ authentication. Message authentication provides assurance of the identity of the originator of the message. Entity authentication provides assurance of the identity of originator of the message, as well as assurance of the active participation of the originator of the message.
FIG. 6 shows a communication channel where two parties (A and B) communicate using a protocol for exchanging messages. Party A is the sender of the message M, and party B is the receiver. Depending upon the type of communication network, party B would like at least three (3) pieces of information on receipt of the message: (1) an assurance of the identity of the party that sent the message M (commonly referred to as ‘message’ authentication), (2) evidence that the message M was not modified during transmission (data integrity), and (3) an indication that party A (i.e., the sender) was active at the time the message was sent (commonly referred to as ‘entity’ authentication).
As stated above, message authentication provides assurance of the identity of party A, the originator of the message M. Message authentication also includes evidence of data integrity because if the message M is modified during transmission, party A cannot be the originator. Entity authentication, on the other hand, assures party B of not only the identity of party A, but also his active participation. Sometimes, two parties need to authenticate each other for messages to flow in either direction. Challenge-response protocols based on symmetric or public key schemes, and zero-knowledge protocols are commonly used for mutual authentication.
Although message authentication provides no guarantees of timeliness or uniqueness, it is very useful in communications where one party (e.g., party A) is not active during the execution of the message protocol. To avoid replay attacks (i.e., where a pirate masquerades as party A, and sends a previously used message in an attempt to obtain the protocol), time variant data (e.g., sequence numbers, time stamps, etc.) may be added to the message M.
The cryptographic process known as “hashing” is an essential part of data integrity and message authentication schemes. A hash function takes a message of arbitrary finite length and produces an output of fixed length. In cryptographic applications, the hash value is considered to be a shorter representation of the actual message. Hash functions may be classified into two groups: (1) unkeyed hash functions (i.e., the message is the only input parameter), and (2) keyed hash functions (i.e., the message and a secret key are the input parameters).
A particular class of unkeyed hash functions contains Manipulation Detection Codes (MDCs). MDCs differ in the way in which the message M is compressed. Some examples are: (a) hash functions based on block ciphers, (b) hash functions based on modular arithmetic, and (c) customized hash functions.
The keyed hash functions that are used for message authentication are grouped under Message Authentication Codes (MACs). MACs can be customized, constructed using block ciphers, or derived from MDCs.
Message authentication methods may be classified by how they exploit symmetric or public key ciphers: (a) MACs, (b) message encryption, and (c) digital signatures.
FIG. 7 shows a block diagram of a message authentication method using a MAC. The message M is input to a MAC algorithm which computes the MAC using a key K which is shared by both parties (i.e., sender (party A) and receiver (party B)). Party A then appends the MAC to the message M, and sends the composite signal to party B.
FIG. 8 shows a block diagram of a message authentication method using message encryption. Message encryption may be accomplished in two ways, symmetric key encryption and public key encryption. With symmetric key encryption, the message M is encrypted with a symmetric key before transmission to the receiver (e.g., party B). The receiver (e.g., party B) uses a copy of the symmetric key to decrypt the message. With public key encryption, the message M is encrypted using a public key and decrypted using the corresponding private key at the receiver. As shown in FIG. 8, under either method, a message M is input to an encryption algorithm which uses a key K (symmetric or public) to create an encrypted message Ek(M).
FIG. 9 shows a block diagram of a message authentication method using a digital signature. In this method, the sender (e.g., party A) uses a private key (Kprivate) to digitally sign the message M. Depending upon the size of the message M, an appropriate signature algorithm may be used. The receiver (e.g., party B) has assurance that the message M was generated by A because A is the only party who owns the private key.
If a fixed key is used for creation of MACs, message encryption and digital message signing (i.e., all three message authentication types), the security level would be limited, thereby exposing the system to cryptanalysis.
With respect to the ‘MAC’ method, the symmetric key shared by the sender and the receiver needs to used for all messages during its lifetime. This makes this method vulnerable to attacks for key recovery and MAC forgery. There are two possible attacks: (1) attacks on the key space, and (2) attacks on the MAC value. If the pirate can determine the MAC key, he or she would be able to create a MAC value for any message. For a key size of ‘t’ bits and a fixed input, the probability of finding the correct n-bit MAC is about 2−t. The objective of MAC forgery is to create a MAC for a given message, or to find a message for a given MAC without knowing the key. For an n-bit MAC algorithm, the probability of meeting this objective is about 2−n. In sum, the effort needed for a brute force attack on a MAC algorithm would be the minimum (2t, 2n).
With respect to the message encryption method, this method is also vulnerable to brute force attacks. For example, for a 56-bit DES (symmetric) algorithm, the key may be determined by testing all 255 DES operations. More efficient attacks like linear or differential cryptanalysis allow key recovery with less processor time.
With respect to the digital signature method, no public key signature algorithm has been proven secure. The security of public key algorithms is based on the difficulty of computing discrete logarithms, or factoring large numbers. With a fixed public/private key pair, attacks are possible using the public key or signatures on messages. In some applications, the authenticity of the sender's public key is a major problem requiring complex public key infrastructures.
Thus, there is presently a need for a system for providing message authentication which provides a higher degree of security, but which does not used fixed keys.